#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <cstring>
#include <string>

using namespace std;

typedef long long int64;

const int maxM = 10000;
const int mod = 1000000007;

bool is_prime[maxM + 1];

void init()
{
	is_prime[0] = is_prime[1] = false;

	for (int i = 2; i <= maxM; ++i) is_prime[i] = true;
	
	for (int i = 2; i <= maxM; ++i) if (is_prime[i])
		for (int j = i * i; j <= maxM; j += i)
			is_prime[j] = false;
}

const int cc[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

int *f[100000];

void release(int i)
{
	if (f[i])
		delete [] f[i];
	f[i]  = 0;
}

void prepare(int i, int m)
{
	if (f[i])
		release(i);
    f[i] = new int[m + 1];
	memset(f[i], 0, sizeof(int) * (m + 1));
}


int main()
{
	int nCase;
	
	init();
	
	cin >> nCase;
	
	memset(f, 0, sizeof(f));
	
	while (nCase--)
	{
		int n, m;
		cin >> n >> m;
		
		for (int i = 0; i < 10; ++i)
			prepare(i, m);
			
		f[0][0] = 1;
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < m; ++j) if (f[i][j] > 0)
			    for (int k = 0; k < 10; ++k) if (i + cc[k] <= n)
			    {
					if (i == 0 && k == 0)
						continue;
					int x = i + cc[k];
					int y = (j * 10 + k) % m;
//					cout << x << ' ' << y << endl;
					f[x][y] += f[i][j];
					if (f[x][y] >= mod)
						f[x][y] -= mod;
				}
		   prepare(i + 10, m);
		   release(i);
		}
		
		int ret = 0;
		for (int j = 0; j < m; ++j)
		    if (is_prime[j])
		    {
				ret += f[n][j];
				if (ret >= mod) ret -= mod;
			}
		cout << ret << endl;
	}
}
